// Tags: BinarySearch, DP
#include <algorithm>
#include <cstdio>
#include <cstring>

const int N = 1e2 + 5;
int n, m, f[N], d[2][N];

inline bool check(int mid) {
  memset(f, -0x3f, sizeof(f));
  f[0] = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = m; ~j; --j) {
      for (int k = 0; k <= std::min(mid / d[0][i], j); ++k) {
        f[j] =
            std::max(f[j], f[j - k] + (mid - k * d[0][i]) / d[1][i]);
      }
    }
  }
  return f[m] >= m;
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("testdata.in", "r", stdin);
  freopen("testdata.out", "w", stdout);
#else
  freopen("software.in", "r", stdin);
  freopen("software.out", "w", stdout);
#endif
#endif

  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d%d", &d[0][i], &d[1][i]);
  int l = 0, r = 1e9, mid;
  while (l < r) {
    mid = (l + r) >> 1;
    if (check(mid)) r = mid;
    else
      l = mid + 1;
  }
  printf("%d", r);
  return 0;
}